package lc.递归;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/25
 */
public class 剑指Offer13_机器人的运动范围 {

    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0,0,m,n,k,visited);
    }

    private int dfs(int x, int y, int m, int n, int k, boolean[][] visited) {
        if (x >= m  || y >= n || visited[x][y] || (x % 10 + x / 10 + y % 10 + y / 10) > k) {
            return 0;
        }
        visited[x][y] = true;
        return 1 + dfs(x + 1,y,m,n,k,visited) + dfs(x,y + 1,m,n,k,visited);
    }
}
